{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Equal Row and Column Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: equalPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相等行列对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、大小为 <code>n x n</code> 的整数矩阵 <code>grid</code> ，返回满足 <code>R<sub>i</sub></code><em> </em>行和<em> </em><code>C<sub>j</sub></code><em> </em>列相等的行列对<em> </em><code>(R<sub>i</sub>, C<sub>j</sub>)</code><em> </em>的数目<em>。</em></p>\n",
    "\n",
    "<p>如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/01/ex1.jpg\" style=\"width: 150px; height: 153px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[3,2,1],[1,7,6],[2,7,7]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>存在一对相等行列对：\n",
    "- (第 2 行，第 1 列)：[2,7,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/01/ex2.jpg\" style=\"width: 200px; height: 209px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>存在三对相等行列对：\n",
    "- (第 0 行，第 0 列)：[3,1,2,2]\n",
    "- (第 2 行, 第 2 列)：[2,4,2,2]\n",
    "- (第 3 行, 第 2 列)：[2,4,2,2]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 200</code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [equal-row-and-column-pairs](https://leetcode.cn/problems/equal-row-and-column-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [equal-row-and-column-pairs](https://leetcode.cn/problems/equal-row-and-column-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,2,1],[1,7,6],[2,7,7]]', '[[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        gridclone = [[0] * n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                e = grid[i][j]\n",
    "                gridclone[j][i] = e\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            r = grid[i]\n",
    "            for j in range(n):\n",
    "                c = gridclone[j]\n",
    "                if r == c:\n",
    "                    result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid[0]), len(grid)\n",
    "        cow = [[] for _ in range(n)]\n",
    "        for j in range(m):\n",
    "            for i in range(n):\n",
    "                cow[j] += [grid[i][j]]\n",
    "        for i in range(n):\n",
    "            grid[i] = '|'.join(list(map(str,grid[i])))\n",
    "        for i in range(m):\n",
    "            cow[i] = '|'.join(list(map(str,cow[i])))\n",
    "        d1, d2 = {}, {}\n",
    "        for l in grid:\n",
    "            if l in d1:\n",
    "                d1[l] += 1\n",
    "            else:\n",
    "                d1[l] = 1\n",
    "        for l in cow:\n",
    "            if l in d2:\n",
    "                d2[l] += 1\n",
    "            else:\n",
    "                d2[l] = 1\n",
    "        ans = 0\n",
    "        for k in d1:\n",
    "            if k in d2:\n",
    "                ans += d1[k] * d2[k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        matrix = [list(row) for row in zip(*grid)]\n",
    "        #print(matrix)\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(matrix)):\n",
    "                if grid[i] == matrix[j]:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid) \n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                flag = True\n",
    "                for k in range(n):\n",
    "                    if grid[i][k] != grid[k][j]:\n",
    "                        flag = False \n",
    "                        break\n",
    "                if flag:\n",
    "                    cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        cnt = Counter(tuple(row) for row in grid)\n",
    "        return sum(cnt[col] for col in zip(*grid))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for i in grid:\n",
    "            d[tuple(i)] += 1\n",
    "        \n",
    "        n = len(grid)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            t = []\n",
    "            for j in range(n):\n",
    "                t.append(grid[j][i])\n",
    "            res += d[tuple(t)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "    #     res, n = 0, len(grid)\n",
    "    #     for row in range(n):\n",
    "    #         for col in range(n):\n",
    "    #             if self.equal(row,col,n,grid):\n",
    "    #                 res+=1\n",
    "    #     return res\n",
    "    # def equal(self,row: int, col: int, n: int, grid: List[List[int]]) -> bool:\n",
    "    #     for i in range(n):\n",
    "    #         if grid[row][i] != grid[i][col]:\n",
    "    #             return False\n",
    "    #     return True\n",
    "\n",
    "\n",
    "        grid_trans = list(zip(*grid))[::-1]\n",
    "        # grid_trans = grid_trans[::-1]\n",
    "        res = 0\n",
    "        while grid:\n",
    "            num = tuple(grid.pop())\n",
    "            for num_trans in grid_trans:\n",
    "                if tuple(num_trans) ==  num:\n",
    "\n",
    "                    res+=1\n",
    "        return res\n",
    "\n",
    "        # res, n = 0, len(grid)\n",
    "        # #Counter({(3, 2, 1): 1, (1, 7, 6): 1, (2, 7, 7): 1}) \n",
    "        # cnt = Counter(tuple(row) for row in grid)\n",
    "        # res = 0\n",
    "        # for j in range(n):\n",
    "        #     res+=cnt[tuple([grid[i][j] for i in range(n)])]\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        res, n = 0, len(grid)\n",
    "        for row in range(n):\n",
    "            for col in range(n):\n",
    "                if self.equal(row, col, n, grid):\n",
    "                    res += 1\n",
    "        return res\n",
    "    \n",
    "    def equal(self, row: int, col: int, n: int, grid: List[List[int]]) -> bool:\n",
    "        for i in range(n):\n",
    "            if grid[row][i] != grid[i][col]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        # 比较第i行和第j列是否相等\n",
    "        n = len(grid)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans += all(grid[i][k] == grid[k][j] for k in range(n))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        dict1 = {}\n",
    "        \n",
    "\n",
    "        def getStr(array):\n",
    "            return '_'.join([str(item) for item in array])\n",
    "\n",
    "        for item in grid:\n",
    "            key = getStr(item)\n",
    "            if(key not in dict1):\n",
    "                dict1[key] = 0\n",
    "            dict1[key] = dict1[key] + 1\n",
    "        sum1 = 0\n",
    "        for i in range(len(grid[0])):\n",
    "            key = getStr([item[i] for item in grid])\n",
    "            if( key in dict1):\n",
    "                sum1 = sum1 + dict1[key]\n",
    "        return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "\n",
    "        def equal(row_idx, col_idx):\n",
    "            for i in range(n):\n",
    "                if grid[row_idx][i] != grid[i][col_idx]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                if equal(row, col):\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        count=Counter(tuple(i) for i in grid)\n",
    "        for i in zip(*grid):\n",
    "            ans+=count[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        count=Counter(tuple(i) for i in grid)\n",
    "        print(count)\n",
    "        for i in zip(*grid):\n",
    "            if i in count:\n",
    "                ans+=count[i]\n",
    "        return  ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalPairs(self, grid: List[List[int]]) -> int:\n",
    "        grid_row_frequency = {}\n",
    "        for row in grid:\n",
    "            key = tuple((s) for s in row)\n",
    "            if key not in grid_row_frequency.keys():\n",
    "                grid_row_frequency[key] = 1\n",
    "            else:\n",
    "                grid_row_frequency[key] += 1\n",
    "\n",
    "        print(grid_row_frequency)\n",
    "        count = 0\n",
    "        for i in range(len(grid[0])):\n",
    "            col = [row[i] for row in grid]\n",
    "            key = tuple(s for s in col)\n",
    "            if key in grid_row_frequency.keys():\n",
    "                count += grid_row_frequency[key]\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
